package 二分答案法与相关题目;

// 分割数组的最大值(画匠问题)
// 给定一个非负整数数组 nums 和一个整数 m
// 你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
// 测试链接 : https://leetcode.cn/problems/split-array-largest-sum/

public class Code02_SplitArrayLargestSum {

    // 时间复杂度O(n * log(sum))，额外空间复杂度O(1)
    public static int splitArray(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int ans = 0;
        // 答案范围：[0,sum]二分
        for(int l = 0, r = sum, mid; l <= r; ){
            // 中点mid
            mid = l + ((r - l) >> 1);
            // 必须让数组每一部分的累加和 <= mid，请问划分成几个部分才够!
            // （是让每一个子数组的累加和 在 <= mid 的情况下尽量大，看能划分出几个子数组）
            // 如果结果 <= k，则说明 使用 mid-sum 这部分累加和划分出来的子数组数量都是 <= k 的，向左侧二分
            if(f(nums, mid) <= k){
                // 达标
                ans = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return ans;
    }

    // 必须让数组arr每一部分的累加和 <= limit，请问划分成几个部分才够!
    // 返回需要的部分数量
    public static int f(int[] nums, int limit){
        // 划分的子数组个数
        int parts = 1;
        // 每个子数组部分的累加和
        int sum = 0;
        for (int num : nums) {
            // 如果数组的单个数的大小 超过了limit，
            // 则说明不能进行划分，返回整数最大值，向右侧进行二分
            if(num > limit){
                return Integer.MAX_VALUE;
            }else if (sum + num > limit){ // 一个子数组的部分结束了
                parts++;
                // 下一个子数组的开始部分
                sum = num;
            }else {
                sum += num;
            }
        }
        return parts;
    }
}
